Möbius Inversion Formula

Muhammad Haris Rao

Recall that an arithmetic funciton is simply a complex valued function on the positive integers. Given two ariithmetic functions $f, g : \mathbb{Z}_{> 0} \longrightarrow \mathbb{C}$, their convolution is defined as \begin{align*} \left( f * g \right) \left(n \right) = \sum_{d \mid n} f(d) g \left( \frac{n}{d} \right) \end{align*} Clearly, convolution is commutative. What is not immediately obvious is that it is associative as well.

Proposition: The convolution operation on arithmetic functions is associative

Proof. Let $f, g, h : \mathbb{Z}_{> 0} \longrightarrow \mathbb{C}$ be arithmetic functions. Then, \begin{align*} \left( \left( f * g \right) * h \right) \left( n \right) &= \sum_{d \mid n} \left( f * g \right) \left( d \right) h \left( \frac{n}{d} \right) \\ &= \sum_{d \mid n} \sum_{k \mid d } f \left( k \right) g \left( \frac{d}{k} \right) h \left( \frac{n}{d} \right) \\ &= \sum_{d \mid n} \sum_{k \mid d } f \left( k \right) g \left( \frac{n/k}{n/d} \right) h \left( \frac{n}{d} \right) \end{align*} We will interchange the summations. We are summing over the dividors $d$ of $n$, and then over the dividors $k$ of $d$. The values of $k$ are of course dividors of $n$ as well, so this is the same as doing a summation over the dividors $k$ of $n$, and then over dividors $d$ of $n$ such that $k$ divides $d$. Clearly, for fixed values of $k,d$ with $k,d \mid n$, we will have $d \mid k$ if and only if $(n/d) \mid (n/k)$. Hence, \begin{align*} \sum_{d \mid n} \sum_{k \mid d } f \left( k \right) g \left( \frac{n/k}{n/d} \right) h \left( \frac{n}{d} \right) &= \sum_{k \mid n} \sum_{(n/d) \mid (n/k)} f \left( k \right) g \left( \frac{n/k}{n/d} \right) h \left( \frac{n}{d} \right) \\ &= \sum_{k \mid n} f \left( k \right) \sum_{\ell \mid (n/k)} g \left( \ell \right) h \left( \frac{n/k}{\ell} \right) \\ &= \sum_{k \mid n} f \left( k \right) \left( g * h \right) \left( \frac{n}{k} \right) \\ &= \left( f * \left( g * h \right) \right) \left( n \right) \end{align*}

It is easily checked that if one defines the arithmetical function \begin{align*} \varepsilon(n) &= \begin{cases} 1 &\text{ , if $n = 1$} \\ 0 &\text{ , if $n > 1$} \end{cases} \end{align*} Then always $\varepsilon * f = f * \varepsilon = f$ for any arithmetical function $f$. That is to say, $\varepsilon$ acts as a unit. Under fairly general conditions, inverses also exist.

Proposition: If $f : \mathbb{Z}_{> 0} \longrightarrow \mathbb{C}$ is an arithmetical function. Then there exists a unique $g: \mathbb{Z}_{> 0} \longrightarrow \mathbb{Z}$ such that \begin{align*} \left( f * g \right) \left( n \right) = \left( g * f \right) \left( n \right) = \varepsilon(n) \end{align*} if and only if $f(1) \ne 0$.

Proof. The foward direction is provd by noting that \begin{align*} 1 = \varepsilon(1) &= f(1) g(1) \end{align*} So both $f(1)$ and $g(1)$ are non-zero.

Now for the converse. Begin by defining $g(1) = 1/f(1)$ and define $g(n)$ for $n > 1$ recursively by \begin{align*} g(n) &= - \frac{1}{f(1)} \sum_{d \mid n, d > 1} f(d) g \left( \frac{n}{d} \right) \end{align*} This is clearly well-defined since the value of $g(n)$ depends only on values of $f$ which are given, and values of $g(1),g(2), \cdots, g(n - 1)$. The fact that $(f * g)(1) = 1$ is clear. For $n > 1$, we have \begin{align*} \left( f * g \right) (n) &= \sum_{d \mid n} f \left( d \right) g \left( \frac{n}{d} \right) = \sum_{d \mid n, d > 1} f \left( d \right) g \left( \frac{n}{d} \right) + f(1) g(n) \end{align*} Substituting our expression for $g(n)$ in terms of $f$ and $g(1), g(2), \cdots, g(n - 1)$ yields 0. Moreover, for the above quantity to be 0, the value of $g(n)$ is forced to be what we have in the recursion which proves uniqueness.

Definiting the addition of arithmetical functions pointwise, it is easily checked that conclution distributes over addition. We have the following result then:

Theorem: The set of arithmetical functions forms a unital commutative ring under pointwise addition and convlution, where the additive identity is the arithmetical function evaluating to 0 everywhere, and the multiplicative identity is $\varepsilon$. The units of this ring are precisely the functions which are nonzero at the argument 1.

Let $\{ p_k \}_{k \ge 1}$ be the prime integers, and let $n$ be a positive integer whose prime factorisation is $n = \prod_{k \ge 1} p_k^{\nu_k}$. The Möbius function is defined as \begin{align*} \mu(n) = \mu \left( \prod_{k \ge 1} p^{\nu_k} \right) &= \begin{cases} 0 &\text{ , if $\nu_k > 1$ for some $k$} \\ (-1)^{\sum_{k \ge 1} \nu_k} &\text{ , otherwise} \end{cases} \end{align*} The important property of $\mu$ is the following:

Proposition: For all $n \ge 1$, \begin{align*} \sum_{d \mid n} \mu(d) &= \begin{cases} 1 &\text{ , if $n = 1$} \\ 0 &\text{ , if $n > 1$} \end{cases} \end{align*}

Proof. The result for $n = 1$ is obvious, so suppose $n > 1$. Consider $n$ as a product of primes $n = \prod_{k = 1}^N p_{\ell_k}^{\nu_{\ell_k}}$ with each $\nu_k \ge 1$ and $\ell_1 < \ell_2 < \cdots < \ell_N$. Then the square free factors of $n$ are \begin{align*} F &= \left\{ \prod_{k \in S} p_{\ell_k} \mid S \subseteq \{ 1,2, \cdots, N \} \right\} \end{align*} Since the value of $\mu$ is zero when the argument is divisible by a square, the desired sum is the sum of $\mu$ over the values in $F$. Letting $n_S = \prod_{k \in S} p_{\ell_k}$ for $S \subseteq \{ 1, 2, \cdots, N \}$, we have \begin{align*} \mu \left( n_S \right) = (-1)^{|S|} \end{align*} Hence, \begin{align*} \sum_{d \mid n} \mu(d) = \sum_{d \in F} \mu(d) = \sum_{S \subseteq \{ 1, \cdots, n \}} (-1)^{|S|} = \sum_{k = 0}^n {n \choose k} (-1)^{k} = \left( 1 + (-1) \right)^n = 0 \end{align*} The third equality is from summing over the values of $|S|$ rather than the choices of $S \subseteq \{ 1, 2, \cdots, n \}$.

Let $u : \mathbb{Z}_{>0} \longrightarrow \mathbb{Z}$ be defined by $u(n) = 1$ for all $n \in \mathbb{Z}_{>0}$. The above statement tells us that the Möbius function is the inverse of $u$ in the sense of convolution. That is, $\varepsilon = u * \mu = \mu * u$. This has the following important consequence:

Theorem (Möbius Inversion): Let $f : \mathbb{Z}_{>0} \longrightarrow \mathbb{C}$ be an arithmetical function, and let $g$ be the divisor sum of $f$. That is, $g : \mathbb{Z}_{>0} \longrightarrow \mathbb{C}$ is \begin{align*} g(n) &= \sum_{d \mid n} f(d) \end{align*} Then $f$ can be written in terms of $g$ as \begin{align*} f(n) &= \sum_{d \mid n} \mu(d) g \left( \frac{n}{d} \right) \end{align*} In other words, $f$ is the convolution $g * \mu$.